package com.hdu.other.tanxin;

import java.util.List;
import java.util.TreeSet;

public class lc632 {
    class Solution {
        public int[] smallestRange(List<List<Integer>> nums)
        {
            TreeSet<Node> set = new TreeSet<>((a, b)->{
                if (a.v != b.v) return a.v - b.v;
                else return a.i - b.i;
            });

            for (int i = 0; i < nums.size(); i++) {
                int curI = i;
                int curJ = 0;
                int curV = nums.get(i).get(0);
                set.add(new Node(curV, curI, curJ));
            }

            int min = Integer.MAX_VALUE;
            int a = 0, b = 0;
            while (set.size() == nums.size())
            {
                Node maxNode = set.last();
                Node minNode = set.pollFirst();
                if (maxNode.v - minNode.v < min)
                {
                    min = maxNode.v - minNode.v;
                    a = minNode.v;
                    b = maxNode.v;
                }
                int curI = minNode.i;
                int curJ = minNode.j;
                if (curJ + 1 < nums.get(curI).size())
                {
                    int nextV = nums.get(curI).get(curJ + 1);
                    int nextJ = curJ + 1;
                    int nextI = curI;
                    set.add(new Node(nextV, nextI, nextJ));
                }
            }
            return new int[]{a, b};
        }

        class Node
        {
            int v;
            int i;
            int j;

            public Node(int v, int i, int j)
            {
                this.v = v;
                this.i = i;
                this.j = j;
            }
        }
    }
}
